CodeForces#752 Div3

本文最后更新于:2 个月前

传送门:https://codeforces.com/contest/1619

A. Square String?

对半匹配


B. Squares and Cubes

1~n完全平方数或者完全立方数的数量,先预处理所有完全平方数数组和完全立方数数组。

然后遍历小于n的完全立方数数量cnt1,找到其中也是完全平方数的数量cnt2,再找到所有小于n的完全平方数数量cnt3,显然,答案就是cnt1 + cnt3 - cnt2


C. Wrong Addition

实际上就是把进位分离出来的一个竖式加法,我们要去做这种模式下的一个减法。那做法就很简单了,减出负数就进位就可以了。


D. New Year’s Problem

You can get English version here.

官方给出的解法是二分答案,但是我在评论区看到一个更有意思的解法,公式如下:

解释如下:

根据题意,首先容易得到 $ans \leq minTop1ByFriends$​

规定a[i][j]表示礼物j对人i的贡献

  1. 让我们先假设$n-1 \leq m$​
  • 下面给出一个买礼物的策略:

    • 选择某一个人I,找到他最喜欢的礼物J,并且先假设a[I][J] = max{ a[1][J] , a[2][J] , ... , a[n][J] }(即这个礼物最被I喜欢),我们称之为假设A
    • 找到a[1][J] , a[2][J] , ... , a[n][J]中的大项(Top2),并找到该对应的I',于是已经有2个人的礼物被安排好了

      • 这两个人的joy分别是top1ByFriends[I]top2ByShops[J]
    • 对于剩下的n-2个人,必定能找到他们最喜欢的礼物

      • 对于这些人,他们的joy分别是top1ByFriends[i]
    • 不难得到,在这种策略下,遍历所有的“某一个人I”,可以证明,对于某一个确定的I,在假设A成立的情况下,这种策略是可行的,而在这些所有策略里找最大值,容易得到$ans\leq maxTop2ByShops$​​。​
    • 现在我们来考虑假设A不成立的情况,显然,这种情况不影响我们的结论,因为此时top1ByFriends[I]<top2ByShops[J],答案就主要由top1ByFriends[I]决定,我们不再需要关心I'到底是否是次大还是最大,只要比I的大就行了
  • 所以

  • 我们再来看取等问题

    • 当$minTop1ByFriends \leq maxTop2ByShops$时,我们取I为这个取到minTop1ByFriensI,按照上述策略,可取等
    • 当$minTop1ByFriends \geq maxTop2ByShops$时,我们取J为这个取到maxTop2ByShopsJ,并选取该J对应的Top1ByShops对应的I,按照上述策略,可取等
  • 所以可以取等,所以

  1. 对于$n-1> m$的情况,我在这里做了详细解释

E. MEX and Increments

1.首先解决有没有策略的问题

只要存在至少k个小于k的数,就可以实现MEX = k,对于等于k的这些要通过把他们变大来让他们都不等于k

2.解决最优策略的问题

很容易理解可以通过递推实现,假设实现MEX = k-1最少需要p步,其中由q步用来将等于k-1的数变成k(即原数列中存在q个等于k-1的数),q >= 0,等于k的数一共由q'个(即需要q'步来让它们变成k+1),那么实现MEX = k所需要的最少的步骤数即为p - q + q' + delP,其中:

  • 如果q = 0delP最大的空闲的数
  • 如果q > 0delP = 0

而所谓的空闲的数,就是在实现MEX = k-1后还剩下的多余的小于k-1的数

注意优化查找空闲的数这个步骤


未经允许禁止用于商业用途,转载请标注出处和作者!

 目录

(っ*´Д`)っ㊖ 疯 狂 暗 示 (っ*´Д`)っ㊖